#include<iostream>

using namespace std;
template<class K,class V>
struct BSKVNode
{
	BSKVNode<K, V>* _left;
	BSKVNode<K, V>* _right;

	const K _key;
	V _value;
	BSKVNode(const K& key, const V& value)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
		, _value(value)
	{}
};


template<class K,class V>
class BSKVTree
{
	typedef BSKVNode<K,V> Node;
public:

	void inOrder()
	{
		_inOrder(_root);
		cout << endl;
	}

	bool eraseR(const K& key)
	{
		return _eraseR(_root, key);
	}

	Node* findR(const K& key)
	{
		return _findR(_root, key);
	}

	bool insertR(const K& key, const V& value)
	{
		return _insertR(_root, key, value);
	}

private:
	bool _eraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;

		if (root->_key < key)
		{
			_eraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			_eraseR(root->_left, key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* minright = root->_right;
				while (minright->_left)
				{
					minright = minright->_left;
				}

				swap(root->_key, minright->_key);
				return _eraseR(root->_right, key);
			}

			delete del;
			return true;
		}
	}

	Node* _findR(Node* root, const K& key)
	{
		if (root == nullptr)
			return nullptr;

		if (root->_key < key)
		{
			_findR(root->_right, key);
		}
		else if (root->_key > key)
		{
			_findR(root->_left, key);
		}
		else
		{
			return root;
		}
	}

	bool _insertR(Node*& root, const K& key,const V& value)
	{
		if (root == nullptr)
		{
			root = new Node(key, value);
			return true;
		}

		if (root->_key < key)
		{
			_insertR(root->_right, key, value);
		}
		else if (root->_key > key)
		{
			_insertR(root->_left, key, value);
		}
		else
		{
			return false;
		}
	}

	void _inOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_inOrder(root->_left);
		cout << root->_key << ":" << root->_value << endl;
		_inOrder(root->_right);
	}

	Node* _root = nullptr;
};